//字母异位词分组

package Leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class solution_049 {
    public static List<List<String>> groupAnagrams(String[] strs) {
        // 存储最终结果
        List<List<String>> result = new ArrayList<>();
        // 存储不同字母组合
        // List<Map<Character, Integer>> letters = new ArrayList<>();
        List<List<Character>> letters = new ArrayList<>();
        // 存储相同字母组合的数组下标
        List<List<Integer>> index = new ArrayList<>();
        for (int i = 0; i < strs.length; i++) { // 遍历字符串数组
            int j = 0;
            for (j = 0; j < letters.size(); j++) { // 遍历哈希表
                int k = 0;
                // List<Character> combination = letters.get(j);
                List<Character> combination = new ArrayList<>();
                combination.addAll(letters.get(j));
                for (k = 0; k < strs[i].toCharArray().length; k++) { // 遍历字符串的每个字符
                    // if (letters.get(j).containsKey(strs[i].toCharArray()[k]) == false) //
                    // 如果有一个不匹配就直接推出
                    // break;
                    if (combination.contains(strs[i].toCharArray()[k]) == false)
                        break;
                    else {
                        for (int m = 0; m < combination.size(); m++)
                            if (combination.get(m) == strs[i].toCharArray()[k]) {
                                combination.remove(m);
                                break;
                            }
                    }

                }
                // System.out.println(strs[i].toCharArray().length);
                // System.out.println(letters.get(j).size());
                if (k == strs[i].toCharArray().length && k == letters.get(j).size()) { //
                    // 如果字母组合相同,右边条件用于判定子集的情况
                    // if (combination.size() == 0) {
                    index.get(j).add(i);
                    break;
                }
            }
            if (letters.size() == 0 || j == letters.size()) {
                // Map<Character, Integer> hashmap = new HashMap<>();
                List<Character> letterCombination = new ArrayList<>();
                for (int k = 0; k < strs[i].toCharArray().length; k++)
                    letterCombination.add(strs[i].toCharArray()[k]);
                // hashmap.put(strs[i].toCharArray()[k], k);
                // letters.add(hashmap);
                letters.add(letterCombination);
                List<Integer> list = new ArrayList<>();
                list.add(i);
                index.add(list);
            }
        }

        for (List<Integer> list : index) {
            List<String> ans = new ArrayList<>();
            for (int l : list) {
                ans.add(strs[l]);
            }
            result.add(ans);
        }
        return result;
    }

    public static void main(String[] args) {
        String[] strs = new String[] { "hhhhu", "hhhuh", "hhuhh", "tittt", "tttti", "tttit" };
        System.out.println(groupAnagrams(strs));
    }
}

public class Solution049 {
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hashmap = new HashMap<>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = hashmap.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            hashmap.put(key, list);
        }
        return new ArrayList<List<String>>(hashmap.values());
    }
}
